package com.lw.leetcode.dp.c;

import com.lw.test.util.Utils;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * 2484. 统计回文子序列数目
 *
 * @author liw
 * @version 1.0
 * @date 2023/1/11 10:38
 */
public class CountPalindromes {

    public static void main(String[] args) {
        CountPalindromes test = new CountPalindromes();

        // 2
//        String s = "103301";

        // 21
//        String s = "0000000";

        // 2
//        String s = "9999900000";

        //
        String s = Utils.getStr(10000, '0', '9');

        int i = test.countPalindromes(s);
        System.out.println(i);
    }

    public int countPalindromes(String s) {
        int length = s.length();
        if (length < 5) {
            return 0;
        }
        char[] chars = s.toCharArray();
        int size = 100;
        long[][] arr = new long[length][size];
        int[] counts = new int[10];
        for (int i = 0; i < length; i++) {
            int c = chars[i] - 48;
            int t = c * 10;
            long[] items = arr[i];
            if (i != 0) {
                long[] lasts = arr[i - 1];
                System.arraycopy(lasts, 0, items, 0, size);
                for (int j = 0; j < 10; j++) {
                    items[t + j] = ( items[t + j] + counts[j]) % 1000000007;
                }
            }
            counts[c]++;
        }
        Arrays.fill(counts, 0);
        long sum = 0;
        long[] s2 = new long[100];
        for (int i = length - 1; i > 1; i--) {
            long[] s1 = arr[i - 1];
            for (int j = 0; j < size; j++) {
                sum = (sum + s1[j] * s2[j]) % 1000000007;
            }
            int c = chars[i] - 48;
            int t = c * 10;
            for (int j = 0; j < 10; j++) {
                s2[t + j] = (s2[t + j]+ counts[j]) % 1000000007;
            }
            counts[c]++;
        }
        return (int) sum;
    }

}
